#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 节点结构体（模拟 Python 的 Node 类）
 * 封装行、列、元素值、父节点指针，通过函数访问成员（模拟 @property）
 */
typedef struct Node {
    int line;          // 行号
    int column;        // 列号
    double element;    // 元素值
    struct Node *parent; // 父节点指针
} Node;

/**
 * 创建节点（模拟 Python 的 Node.__init__）
 */
Node* node_create(int line, int column, double element, Node *parent) {
    Node *node = (Node*)malloc(sizeof(Node));
    if (!node) {
        fprintf(stderr, "内存分配失败：Node\n");
        return NULL;
    }
    node->line = line;
    node->column = column;
    node->element = element;
    node->parent = parent;
    return node;
}

/**
 * 释放节点内存
 */
void node_destroy(Node *node) {
    if (node) free(node);
}

/**
 * 栈结构体（模拟 Python 的 list 栈）
 */
typedef struct {
    Node **data;   // 节点指针数组
    int size;      // 当前元素数量
    int capacity;  // 容量
} Stack;

/**
 * 创建栈
 */
Stack* stack_create(int init_capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    if (!stack) {
        fprintf(stderr, "内存分配失败：Stack\n");
        return NULL;
    }
    stack->data = (Node**)malloc(init_capacity * sizeof(Node*));
    if (!stack->data) {
        fprintf(stderr, "内存分配失败：Stack data\n");
        free(stack);
        return NULL;
    }
    stack->size = 0;
    stack->capacity = init_capacity;
    return stack;
}

/**
 * 栈扩容（2 倍扩容）
 */
int stack_resize(Stack *stack) {
    int new_cap = stack->capacity * 2;
    Node **new_data = (Node**)realloc(stack->data, new_cap * sizeof(Node*));
    if (!new_data) {
        fprintf(stderr, "栈扩容失败\n");
        return -1;
    }
    stack->data = new_data;
    stack->capacity = new_cap;
    return 0;
}

/**
 * 节点入栈
 */
int stack_push(Stack *stack, Node *node) {
    if (!stack || !node) return -1;
    // 容量不足则扩容
    if (stack->size >= stack->capacity) {
        if (stack_resize(stack) != 0) return -1;
    }
    stack->data[stack->size++] = node;
    return 0;
}

/**
 * 节点出栈（栈顶）
 */
Node* stack_pop(Stack *stack) {
    if (!stack || stack->size == 0) return NULL;
    return stack->data[--stack->size];
}

/**
 * 释放栈内存（仅释放栈结构，节点需单独释放）
 */
void stack_destroy(Stack *stack) {
    if (stack) {
        free(stack->data);
        free(stack);
    }
}

/**
 * 多项式化简核心函数（对齐 Python 的 polynomial_simplify）
 * @param matrix: 二维数组（行优先存储，matrix[line][col] = matrix[line*m + col]）
 * @param n: 矩阵行数
 * @param m: 矩阵列数
 * @param out_len: 输出结果数组长度
 * @return: 化简后的系数数组（成功），NULL（失败）
 */
double* polynomial_simplify(const double *matrix, int n, int m, int *out_len) {
    // 输入校验
    if (!matrix || n <= 0 || m <= 0 || !out_len) {
        fprintf(stderr, "无效输入参数\n");
        return NULL;
    }

    // 初始化结果数组：(m-1)*n + 1 个元素，初始值 0
    int result_len = (m - 1) * n + 1;
    double *result = (double*)calloc(result_len, sizeof(double));
    if (!result) {
        fprintf(stderr, "内存分配失败：result 数组\n");
        return NULL;
    }

    // 创建栈，初始容量为 m（第一行节点数）
    Stack *stack = stack_create(m);
    if (!stack) {
        free(result);
        return NULL;
    }

    // 初始化栈：压入第一行所有节点
    for (int i = 0; i < m; i++) {
        double element = matrix[0 * m + i];  // 行优先索引
        Node *node = node_create(0, i, element, NULL);
        if (!node) {
            // 清理已创建的节点和栈
            while (stack->size > 0) {
                Node *p = stack_pop(stack);
                node_destroy(p);
            }
            stack_destroy(stack);
            free(result);
            return NULL;
        }
        if (stack_push(stack, node) != 0) {
            node_destroy(node);
            while (stack->size > 0) {
                Node *p = stack_pop(stack);
                node_destroy(p);
            }
            stack_destroy(stack);
            free(result);
            return NULL;
        }
    }

    // 深度遍历主循环
    while (stack->size > 0) {
        Node *node = stack_pop(stack);
        int line = node->line;
        int column = node->column;
        double element = node->element;
        printf("element=%.2lf\n", element);  // 对齐 Python 的打印

        if (line == n - 1) {
            // 到达最后一行，计算连乘和次数
            double pi = 1.0;
            int p = 0;
            Node *node_pointer = node;
            while (node_pointer != NULL) {
                pi *= node_pointer->element;
                p += m - node_pointer->column - 1;
                node_pointer = node_pointer->parent;
            }
            // 写入结果数组（防止索引越界）
            int idx = result_len - p - 1;
            if (idx >= 0 && idx < result_len) {
                result[idx] += pi;
            } else {
                fprintf(stderr, "结果数组索引越界：%d\n", idx);
            }
        } else {
            // 压入下一行的所有节点
            for (int c = 0; c < m; c++) {
                double e = matrix[(line + 1) * m + c];
                Node *child = node_create(line + 1, c, e, node);
                if (!child) {
                    // 清理资源
                    node_destroy(node);
                    while (stack->size > 0) {
                        Node *p = stack_pop(stack);
                        node_destroy(p);
                    }
                    stack_destroy(stack);
                    free(result);
                    return NULL;
                }
                stack_push(stack, child);
            }
        }

        // 释放当前节点（已处理完毕）
        node_destroy(node);
    }

    // 清理栈
    stack_destroy(stack);
    *out_len = result_len;
    return result;
}

// 示例测试
int main() {
    // 测试矩阵：2行3列
    double matrix[] = {
        1.0, 2.0, 3.0,  // 第一行
        4.0, 5.0, 6.0   // 第二行
    };
    int n = 2;  // 行数
    int m = 3;  // 列数
    int result_len;

    // 调用化简函数
    double *result = polynomial_simplify(matrix, n, m, &result_len);
    if (!result) {
        return -1;
    }

    // 输出结果
    printf("化简后的多项式系数（最高次到最低次）：\n");
    for (int i = 0; i < result_len; i++) {
        printf("result[%d] = %.2lf\n", i, result[i]);
    }

    // 释放内存
    free(result);
    return 0;
}